package number_62;

public class Solution {
    int ret = 0;
    int m;
    int n;
    //timeout;
    public int uniquePaths1(int m, int n) {
        int[][] visited = new int[n][m];
        this.m = m;
        this.n = n;
        backTrace(visited, 0, 0);
        return ret;
    }

    private void backTrace(int[][] visited, int row, int column) {
        if (row >= n || column >= m) {
            return;
        }
        if (row == n - 1 && column == m - 1) {
            ret++;
            return;
        }
        visited[row][column] = 1;
        int[][] dirs = {{0,1}, {1,0}};
        for (int[] dir : dirs) {
            int x = dir[0] + row;
            int y = dir[1] + column;
            if (x >= n || y >= m) {
                continue;
            }
            if (visited[x][y] == 1) {
                continue;
            }
            backTrace(visited, x, y);
            visited[row][column] = 0;
        }
    }

    //dp;
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }


    public static void main(String[] args) {
        new Solution().uniquePaths(3,2);
    }
}
